/*
 * @lc app=leetcode.cn id=23 lang=java
 *
 * [23] 合并 K 个升序链表
 */

// @lc code=start

import java.util.List;
import java.util.PriorityQueue;

import javax.management.ListenerNotFoundException;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 使用优先级队列---将链表节点放入一个最小堆
        if(lists == null || lists.length == 0) {
            return null;
        }

        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;

        PriorityQueue<ListNode> queue = new PriorityQueue<>(
            lists.length, (a, b)->(a.val - b.val)
        );

        // 将所有链表的头节点放入优先级队列
        for(ListNode head : lists) {
            if(head != null) {
                queue.add(head);
            }
        }

        while(!queue.isEmpty()) {
            // 获取最小节点
            ListNode node = queue.poll();
            p.next = node;
            if(node.next != null) {
                queue.add(node.next);
            }
            p = p.next;
        }
        return dummy.next;
    }

    
}
// @lc code=end

